/**
 * 98. 验证二叉搜索树
 *
 * 【中等】
 *
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 *
 * 有效 二叉搜索树定义如下：
 * · 节点的左子树只包含 小于 当前节点的数。
 * · 节点的右子树只包含 大于 当前节点的数。
 * · 所有左子树和右子树自身必须也是二叉搜索树。
 *
 * 示例 1：
 * 【https://assets.leetcode.com/uploads/2020/12/01/tree1.jpg】
 * 输入：root = [2,1,3]
 * 输出：true
 *
 * 示例 2：
 * 【https://assets.leetcode.com/uploads/2020/12/01/tree2.jpg】
 * 输入：root = [5,1,4,null,null,3,6]
 * 输出：false
 * 解释：根节点的值是 5 ，但是右子节点的值是 4 。
 */

import { TreeNode } from '../utils/tree'

// 递归
var isValidBST = function isValidBST(root: TreeNode | null): boolean {
	let leftVal = -Infinity
	let result = true
	function inorder(root) {
		if (!root) {
			return
		}
		inorder(root.left)
		if (root.val <= leftVal) {
			result = false
			return result
		}
		leftVal = root.val
		inorder(root.right)
	}

	inorder(root)
	return result
}

// 迭代
var isValidBST = function isValidBST(root: TreeNode | null): boolean {
	const stack: Array<TreeNode> = []
	let leftVal = -Infinity
	while (root || stack.length) {
		while (root) {
			stack.push(root)
			root = root.left
		}
		root = stack.pop()!

		// 如果中序遍历得到的节点的值小于等于前一个 leftVal，说明不是二叉搜索树
		if (root.val <= leftVal) {
			return false
		}
		leftVal = root.val

		root = root.right
	}

	return true
}

var isValidBST = function isValidBST(root: TreeNode | null): boolean {
	const dfs = (root, minVal, maxVal) => {
		if (!root) return true

		if (root.val <= minVal || root.val >= maxVal) return false

		return dfs(root.left, minVal, root.val) && dfs(root.right, root.val, maxVal)
	}

	return dfs(root, -Infinity, Infinity)
}
